package com.fw.leetcode.stack;

import com.fw.leetcode.LeetCode;

/**
 * 316. Remove Duplicate Letters
 *
 * Given a string s, remove duplicate letters so that every letter appears once and only once. You must make sure your result is
 * the smallest in lexicographical order among all possible results.
 *
 * Example 1:
 *  Input: s = "bcabc"
 *  Output: "abc"
 *
 * Example 2:
 *  Input: s = "cbacdcbc"
 *  Output: "acdb"
 *
 * Constraints:
 *  1 <= s.length <= 10^4
 *  s consists of lowercase English letters.
 *
 * Note: This question is the same as 1081: https://leetcode.com/problems/smallest-subsequence-of-distinct-characters/
 */
public class Num_0316 implements LeetCode {
    private interface Solution {
        String removeDuplicateLetters(String s);

        default void assertEquals(String s, String expected) {
            if (!expected.equals(removeDuplicateLetters(s))) {
                removeDuplicateLetters(s);
            }
        }
    }

    private static class MySolution implements Solution {

        @Override
        public String removeDuplicateLetters(String s) { // 贪心 + 单调栈：时O(n) 空O(<26)
            /*
             * 去除重复字母（在不打乱字符相对顺序的情况下返回最小字典序）
             * - 观察到字符大小的起伏变化
             *
             * 目标："bcabc"
             * 字典序："abc" < "bca" < "cab"
             *
             * 目标："cbacdcbc"
             * 字典序："acdb"
             *
             * 实现步骤解析：
             * 1.统计字符出现频次
             * 2.用栈原因：考虑一个数组，从s[0]开始依次向其中放入，若不满足则将最近的移除，此即栈结构
             * 3.从栈顶移除条件：
             *  1）s[i] 尚未入栈，或相同字符之前入栈后现在已经出栈
             *  2）s[i] < 栈顶字符，如：栈中 [c,b]，s[2]=a < b|c
             *  3）栈中待移除的字符频次大于 1
             * 4.入栈条件：
             *  1）栈中还未存在该字符
             * 5.贪心：
             *  1）以当前访问字符为截止视角，之后的字符频率不包含已遍历过的，每次都是新的开始
             */
            int[] charNum = new int[26]; // 26个英文小写字符
            for (char ch : s.toCharArray()) { // 统计字符频次
                charNum[ch - 'a']++;
            }
            boolean[] charInStack = new boolean[26]; // 标记字符是否已在栈中
            char[] stack = new char[s.length()]; // 存放字符的栈
            int stackTop = -1; // 栈顶索引
            // 再次遍历目标字符串
            for (char ch : s.toCharArray()) {
                if (!charInStack[ch - 'a']) { // 尚未入栈，[!] 需要套住下面的 while
                    // 尝试移除栈顶字符
                    while (stackTop >= 0 && ch < stack[stackTop]) {
                        if (charNum[stack[stackTop] - 'a'] > 0) { // 字符多次出现，则移除
                            charInStack[stack[stackTop] - 'a'] = false; // [!] 标记出栈字符未入栈，需放在置零前
                            stack[stackTop--] = 0; // 置零
                        } else { // 否则不动
                            break;
                        }
                    }
                    // 将当前字符入栈
                    stack[++stackTop] = ch;
                    charInStack[ch - 'a'] = true; // [!] 标记当前字符已入栈
                }
                charNum[ch - 'a']--; // [!] 每访问过一次，将其出现频率减 1 => [贪心] 以当前截止视角，之后的字符频率不包含已遍历过的
            }
            // 构造结果字符串
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i <= stackTop; i++) {
                sb.append(stack[i]);
            }
            return sb.toString();
        }
    }

    public static void main(String[] args) {
        Solution solution = new MySolution();
        solution.assertEquals("bcabc", "abc");
        solution.assertEquals("cbacdcbc", "acdb");
        solution.assertEquals("cdadabcc", "adbc");
    }
}
